#include <iostream>
#include <string>
#include <stack>

using namespace std;
// 100.00 %
class Solution
{
  public:
	bool isValid(string s)
	{
		stack<char> myStack;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == '{' || s[i] == '[' || s[i] == '(')
				myStack.push(s[i]);
			else
			{
				switch (s[i])
				{
				case '}':
					if (!myStack.empty() && myStack.top() == '{')
					{
						myStack.pop();
						break;
					}
					else
						return false;
				case ']':
					if (!myStack.empty() && myStack.top() == '[')
					{
						myStack.pop();
						break;
					}
					else
						return false;
				case ')':
					if (!myStack.empty() && myStack.top() == '(')
					{
						myStack.pop();
						break;
					}
					else
						return false;
				default:
					break;
				}
			}
		}
		if (myStack.empty())
			return true;
		return false;
	}
};

int main()
{
	string s = "a{sda[das";
	cout << Solution().isValid(s) << endl;
	return 0;
}
